home *** CD-ROM | disk | FTP | other *** search
/ .net 2002 March / DotNetMagazine-Issue107-Coverdisc-NET107-02-03-PCMac.bin / pc / PC Software / picks / HTTrack / httrack-3.22-3.exe / {app} / src / htshash.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-11-17  |  8.6 KB  |  276 lines
  1. /* ------------------------------------------------------------ */
  2. /*
  3. HTTrack Website Copier, Offline Browser for Windows and Unix
  4. Copyright (C) Xavier Roche and other contributors
  5.  
  6. This program is free software; you can redistribute it and/or
  7. modify it under the terms of the GNU General Public License
  8. as published by the Free Software Foundation; either version 2
  9. of the License, or any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19.  
  20.  
  21. Important notes:
  22.  
  23. - We hereby ask people using this source NOT to use it in purpose of grabbing
  24. emails addresses, or collecting any other private information on persons.
  25. This would disgrace our work, and spoil the many hours we spent on it.
  26.  
  27.  
  28. Please visit our Website: http://www.httrack.com
  29. */
  30.  
  31.  
  32. /* ------------------------------------------------------------ */
  33. /* File: httrack.c subroutines:                                 */
  34. /*       hash table system (fast index)                         */
  35. /* Author: Xavier Roche                                         */
  36. /* ------------------------------------------------------------ */
  37.  
  38. #include "htshash.h"
  39.  
  40. /* specific definitions */
  41. #include "htsbase.h"
  42. #include "htsglobal.h"
  43. #include "htsmd5.h"
  44. #include <stdio.h>
  45. #include <stdlib.h>
  46. #include <string.h>
  47. /* END specific definitions */
  48.  
  49. /* Specific macros */
  50. #ifndef malloct
  51. #define malloct malloc
  52. #define freet free
  53. #define calloct calloc
  54. #define strcpybuff strcpy
  55. #endif
  56.  
  57. // GESTION DES TABLES DE HACHAGE
  58. // MÈthode ‡ 2 clÈs (adr+fil), 2e cle facultative
  59. // hash[no_enregistrement][pos]->hash est un index dans le tableau gÈnÈral liens
  60. // #define HTS_HASH_SIZE 8191  (premier si possible!)
  61. // type: numero enregistrement - 0 est case insensitive (sav) 1 (adr+fil) 2 (former_adr+former_fil)
  62. #if HTS_HASH
  63. // recherche dans la table selon nom1,nom2 et le no d'enregistrement
  64. // retour: position ou -1 si non trouvÈ
  65. int hash_read(hash_struct* hash,char* nom1,char* nom2,int type) {
  66.   unsigned int cle;
  67.   int pos; 
  68.   // calculer la clÈ de recherche, non modulÈe
  69.   if (type)
  70.     cle = hash_cle(nom1,nom2);
  71.   else
  72.     cle = hash_cle(convtolower(nom1),nom2);         // case insensitive
  73.   // la position se calcule en modulant
  74.   pos = (int) (cle%HTS_HASH_SIZE);
  75.   // entrÈe trouvÈe?
  76.   if (hash->hash[type][pos] >= 0) {             // un enregistrement avec une telle clÈ existe..
  77.     // tester table de raccourcis (hash)
  78.     // pos est maintenant la position recherchÈe dans liens
  79.     pos = hash->hash[type][pos];
  80.     while (pos>=0) {              // parcourir la chaine
  81.       switch (type) {
  82.       case 0:         // sav
  83.         if (strfield2(nom1,hash->liens[pos]->sav)) {  // case insensitive
  84. #if DEBUG_HASH==2
  85.           printf("hash: found shortcut at %d\n",pos);
  86. #endif
  87.           return pos;
  88.         }
  89.         break;
  90.       case 1:         // adr+fil
  91.         if ((strcmp(nom1,jump_identification(hash->liens[pos]->adr))==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  92. #if DEBUG_HASH==2
  93.           printf("hash: found shortcut at %d\n",pos);
  94. #endif
  95.           return pos;
  96.         }
  97.         break;
  98.       case 2:         // former_adr+former_fil
  99.         if (hash->liens[pos]->former_adr)
  100.         if ((strcmp(nom1,jump_identification(hash->liens[pos]->former_adr))==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  101. #if DEBUG_HASH==2
  102.           printf("hash: found shortcut at %d\n",pos);
  103. #endif
  104.           return pos;
  105.         }
  106.         break;
  107.       }
  108.       // calculer prochaine position dans la chaine
  109.       {
  110.         int old=pos;
  111.         pos=hash->liens[pos]->hash_next[type];   // sinon prochain dans la chaine
  112.         if (old==pos)
  113.           pos=-1;         // erreur de bouclage (ne devrait pas arriver)
  114.       }
  115.     }
  116.     
  117.     // Ok va falloir chercher alors..
  118.     /*pos=hash->max_lien;    // commencer ‡ max_lien
  119.     switch (type) {
  120.     case 0:         // sav
  121.       while(pos>=0) {
  122.         if (hash->liens[pos]->hash_sav == cle ) {
  123.           if (strcmp(nom1,hash->liens[pos]->sav)==0) {
  124.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rÈcent dans shortcut table
  125. #if DEBUG_HASH==2
  126.             printf("hash: found long search at %d\n",pos);
  127. #endif
  128.             return pos;
  129.           }
  130.         }
  131.         pos--;
  132.       }
  133.       break;
  134.     case 1:         // adr+fil
  135.       while(pos>=0) {
  136.         if (hash->liens[pos]->hash_adrfil == cle ) {
  137.           if ((strcmp(nom1,hash->liens[pos]->adr)==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  138.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rÈcent dans shortcut table
  139. #if DEBUG_HASH==2
  140.             printf("hash: found long search at %d\n",pos);
  141. #endif
  142.             return pos;
  143.           }
  144.         }
  145.         pos--;
  146.       }
  147.       break;
  148.     case 2:         // former_adr+former_fil
  149.       while(pos>=0) {
  150.         if (hash->liens[pos]->hash_fadrfil == cle ) {
  151.           if (hash->liens[pos]->former_adr)
  152.             if ((strcmp(nom1,hash->liens[pos]->former_adr)==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  153.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rÈcent dans shortcut table
  154. #if DEBUG_HASH==2
  155.             printf("hash: found long search at %d\n",pos);
  156. #endif
  157.             return pos;
  158.           }
  159.         }
  160.         pos--;
  161.       }
  162.     }*/
  163. #if DEBUG_HASH==1
  164.     printf("hash: not found after test %s%s\n",nom1,nom2);
  165. #endif
  166.     return -1;    // non trouvÈ
  167.   } else {
  168. #if DEBUG_HASH==2
  169.     printf("hash: not found %s%s\n",nom1,nom2);
  170. #endif
  171.     return -1;    // non trouvÈ : clÈ non entrÈe (mÍme une fois)
  172.   }
  173. }
  174.  
  175. // enregistrement lien lpos dans les 3 tables hash1..3
  176. void hash_write(hash_struct* hash,int lpos) {
  177.   unsigned int cle;
  178.   int pos; 
  179.   int* ptr;
  180.   //
  181.   if (hash->liens[lpos]) {                       // on sait jamais..
  182.     hash->max_lien = max(hash->max_lien,lpos);
  183. #if DEBUG_HASH
  184.     hashnumber=hash->max_lien;
  185. #endif
  186.     // ÈlÈment actuel sur -1 (fin de chaine)
  187.     hash->liens[lpos]->hash_next[0]=hash->liens[lpos]->hash_next[1]=hash->liens[lpos]->hash_next[2]=-1;
  188.     //
  189.     cle = hash_cle(convtolower(hash->liens[lpos]->sav),"");    // CASE INSENSITIVE
  190.     pos = (int) (cle%HTS_HASH_SIZE);
  191.     ptr = hash_calc_chaine(hash,0,pos);         // calculer adresse chaine
  192.     *ptr = lpos;                   // noter dernier enregistrÈ
  193. #if DEBUG_HASH==3
  194.     printf("[%d",pos);
  195. #endif
  196.     //
  197.     cle = hash_cle(jump_identification(hash->liens[lpos]->adr),hash->liens[lpos]->fil);
  198.     pos = (int) (cle%HTS_HASH_SIZE);
  199.     ptr = hash_calc_chaine(hash,1,pos);         // calculer adresse chaine
  200.     *ptr = lpos;                   // noter dernier enregistrÈ
  201. #if DEBUG_HASH==3
  202.     printf(",%d",pos);
  203. #endif
  204.     //
  205.     if (hash->liens[lpos]->former_adr) {         // former_adr existe?
  206.       cle = hash_cle(jump_identification(hash->liens[lpos]->former_adr),hash->liens[lpos]->former_fil);
  207.       pos = (int) (cle%HTS_HASH_SIZE);
  208.       ptr = hash_calc_chaine(hash,2,pos);         // calculer adresse chaine
  209.       *ptr = lpos;                   // noter dernier enregistrÈ
  210. #if DEBUG_HASH==3
  211.       printf(",%d",pos);
  212. #endif
  213.     }
  214. #if DEBUG_HASH==3
  215.     printf("] "); fflush(stdout);
  216. #endif
  217.   }
  218. #if DEBUT_HASH
  219.   else {
  220.     printf("* hash_write=0!!\n");
  221.     abortLogFmt("unexpected error in hash_write (pos=%d)" _ pos);
  222.     exit(1);
  223.   }
  224. #endif
  225.   //
  226. }
  227.  
  228. // calcul clÈ
  229. // il n'y a pas de formule de hashage universelle, celle-ci semble acceptable..
  230. unsigned long int hash_cle(char* nom1,char* nom2) {
  231.   /*
  232.   unsigned int sum=0;
  233.   int i=0;
  234.   while(*nom1) {
  235.     sum += 1;
  236.     sum += (unsigned int) *(nom1);
  237.     sum *= (unsigned int) *(nom1++);
  238.     sum += (unsigned int) i;
  239.     i++;
  240.   }
  241.   while(*nom2) {
  242.     sum += 1;
  243.     sum += (unsigned int) *(nom2);
  244.     sum *= (unsigned int) *(nom2++);
  245.     sum += (unsigned int) i;
  246.     i++;
  247.   }
  248.   */
  249.   return md5sum32(nom1)
  250.         +md5sum32(nom2);
  251. }
  252.  
  253. // calcul de la position finale dans la chaine des elements ayant la mÍme clÈ
  254. int* hash_calc_chaine(hash_struct* hash,int type,int pos) {
  255. #if DEBUG_HASH
  256.   int count=0;
  257. #endif
  258.   if (hash->hash[type][pos] == -1)
  259.     return &(hash->hash[type][pos]);    // premier ÈlÈment dans la chaine
  260.   pos=hash->hash[type][pos];
  261.   while(hash->liens[pos]->hash_next[type] != -1) {
  262.     pos = hash->liens[pos]->hash_next[type];
  263. #if DEBUG_HASH
  264.     count++;
  265. #endif
  266.   }
  267. #if DEBUG_HASH
  268.   count++;
  269.   longest_hash[type]=max(longest_hash[type],count);
  270. #endif
  271.   return &(hash->liens[pos]->hash_next[type]);
  272. }
  273. #endif
  274. // FIN GESTION DES TABLES DE HACHAGE
  275.  
  276.